package com.cty.huffmantree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/*
*
* 赫夫曼树的创建
*
*
* */
public class huffmanTree {
    public static void main(String[] args) {
        int[] arr = {10,80,66,7,69,3,5};
        Node root = creatHuffmanTree(arr);
        root.preOrder();
    }
    public static Node creatHuffmanTree(int[] arr) {
        List<Node> list = new ArrayList<>();
        for (int elem: arr) {
            list.add(new Node(elem));
        }
        while (list.size() > 1) {
            Collections.sort(list);
            Node leftNode = list.get(0);
            Node rightNode = list.get(1);
            Node parent = new Node(leftNode.value + rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;
            list.remove(leftNode);
            list.remove(rightNode);
            list.add(parent);
        }
        return list.get(0);
    }
}
